Embodiments of the present invention relate generally to multiprocessors and concurrency in computer systems, and more particularly to techniques for synchronizing processing in systems that process events concurrently.
Computer systems can execute program code instructions using one or more processors that perform operations specified by the instructions. The operations can produce effects on the state of the computer, for example, by changing data stored in the computer's memory. The results produced by the instructions can depend on the state of the computer at the time the instructions are executed and on input received from sources external to the computer system. A set of program code instructions being executed on a computer system is referred to as a “process” or a “thread.” Multiple processes and/or threads can be executed concurrently using one or more processors, so that the processes and threads execute, or at least appear to execute, simultaneously. That is, each process or thread can be executed simultaneously by a different processor, or can be executed on the same processor using a technique such as time slicing to share a single processor among multiple instruction streams. In both scenarios, computer systems can allow the different processes or threads to use a resource, such as memory, that is shared among the processes or threads.
If multiple concurrent processes or threads can access and change the same data value in memory, such as a bank balance variable, then some form of synchronization between the processes or threads is needed, because unsynchronized access to a shared resource can lead to incorrect results as multiple streams of instructions attempt to modify the same resource, e.g., the bank balance variable, at essentially the same time, with each stream expecting that there will be no other modifications to the resource. For example, two different threads may execute the instructions “balance=balance+5” to add $5 to the bank balance variable. If both threads execute these instructions concurrently without synchronization, then incorrect results may occur. The correct result, after execution of both threads, is an increase of the balance by $10. However, adding $5 to the balance can actually involve multiple instructions, such as an instruction to read the balance variable followed by an instruction to add 5 to the value read from the balance variable and store the result in the balance variable. Thus, if both threads execute the first instruction before executing any further instructions, both threads will read the same initial value (e.g., 0 if the balance is initially zero), and add 5.00 to that value, which will result in both threads storing the value 5 in the balance variable, instead of one thread storing 5 and the second thread storing 10, which is the correct behavior. Executing the threads in sequence, e.g., the first thread followed by the second thread, would result in correct behavior, but may be less efficient than executing the threads concurrently. For example, if each thread executes on a corresponding processor, then both threads can be executed in essentially the same amount of time as one thread. If the threads are executed sequentially, then twice as much time may be used for their execution. Further, there are other advantages to executing multiple threads concurrently. For example, resources such as input/output devices can be used more efficiently by concurrent threads.
Therefore, it is desirable to be able to execute threads concurrently, but synchronization between the threads is needed to ensure correct execution. With synchronization, each thread can, for example, request exclusive access to the balance variable before accessing it. Thus each thread will wait until no other threads are accessing the variable before accessing it. Such mutually exclusive access to the shared resource is useful for maintaining correct behavior of concurrent programs. However, constructing concurrent programs that operate correctly and share resources efficiently can be difficult, because identifying the specific instructions that need to be protected by a synchronization technique, such as mutual exclusion, without protecting more of the program than necessary, is a complex task.